// Boost.Polygon library voronoi_graphic_utils.hpp header file

//          Copyright Andrii Sydorchuk 2010-2012.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

// See http://www.boost.org for updates, documentation, and revision history.

#ifndef BOOST_POLYGON_VORONOI_VISUAL_UTILS
#define BOOST_POLYGON_VORONOI_VISUAL_UTILS

#include <stack>
#include <vector>

#include <boost/polygon/isotropy.hpp>
#include <boost/polygon/point_concept.hpp>
#include <boost/polygon/segment_concept.hpp>
#include <boost/polygon/rectangle_concept.hpp>

namespace boost {
	namespace polygon {
		// Utilities class, that contains set of routines handful for visualization.
		template <typename CT>
		class voronoi_visual_utils {
		public:
			// Discretize parabolic Voronoi edge.
			// Parabolic Voronoi edges are always formed by one point and one segment
			// from the initial input set.
			//
			// Args:
			//   point: input point.
			//   segment: input segment.
			//   max_dist: maximum discretization distance.
			//   discretization: point discretization of the given Voronoi edge.
			//
			// Template arguments:
			//   InCT: coordinate type of the input geometries (usually integer).
			//   Point: point type, should model point concept.
			//   Segment: segment type, should model segment concept.
			//
			// Important:
			//   discretization should contain both edge endpoints initially.
			template <class InCT1, class InCT2,
				template<class> class Point,
				template<class> class Segment>
			static
				typename enable_if<
				typename gtl_and<
				typename gtl_if<
				typename is_point_concept<
				typename geometry_concept< Point<InCT1> >::type
				>::type
				>::type,
				typename gtl_if<
				typename is_segment_concept<
				typename geometry_concept< Segment<InCT2> >::type
				>::type
				>::type
				>::type,
				void
				>::type discretize(
				const Point<InCT1>& point,
				const Segment<InCT2>& segment,
				const CT max_dist,
				std::vector< Point<CT> >* discretization) {
					// Apply the linear transformation to move start point of the segment to
					// the point with coordinates (0, 0) and the direction of the segment to
					// coincide the positive direction of the x-axis.
					CT segm_vec_x = cast(x(high(segment))) - cast(x(low(segment)));
					CT segm_vec_y = cast(y(high(segment))) - cast(y(low(segment)));
					CT sqr_segment_length = segm_vec_x * segm_vec_x + segm_vec_y * segm_vec_y;

					// Compute x-coordinates of the endpoints of the edge
					// in the transformed space.
					CT projection_start = sqr_segment_length *
						get_point_projection((*discretization)[0], segment);
					CT projection_end = sqr_segment_length *
						get_point_projection((*discretization)[1], segment);

					// Compute parabola parameters in the transformed space.
					// Parabola has next representation:
					// f(x) = ((x-rot_x)^2 + rot_y^2) / (2.0*rot_y).
					CT point_vec_x = cast(x(point)) - cast(x(low(segment)));
					CT point_vec_y = cast(y(point)) - cast(y(low(segment)));
					CT rot_x = segm_vec_x * point_vec_x + segm_vec_y * point_vec_y;
					CT rot_y = segm_vec_x * point_vec_y - segm_vec_y * point_vec_x;

					// Save the last point.
					Point<CT> last_point = (*discretization)[1];
					discretization->pop_back();

					// Use stack to avoid recursion.
					std::stack<CT> point_stack;
					point_stack.push(projection_end);
					CT cur_x = projection_start;
					CT cur_y = parabola_y(cur_x, rot_x, rot_y);

					// Adjust max_dist parameter in the transformed space.
					const CT max_dist_transformed = max_dist * max_dist * sqr_segment_length;
					while (!point_stack.empty()) {
						CT new_x = point_stack.top();
						CT new_y = parabola_y(new_x, rot_x, rot_y);

						// Compute coordinates of the point of the parabola that is
						// furthest from the current line segment.
						CT mid_x = (new_y - cur_y) / (new_x - cur_x) * rot_y + rot_x;
						CT mid_y = parabola_y(mid_x, rot_x, rot_y);

						// Compute maximum distance between the given parabolic arc
						// and line segment that discretize it.
						CT dist = (new_y - cur_y) * (mid_x - cur_x) -
							(new_x - cur_x) * (mid_y - cur_y);
						dist = dist * dist / ((new_y - cur_y) * (new_y - cur_y) +
							(new_x - cur_x) * (new_x - cur_x));
						if (dist <= max_dist_transformed) {
							// Distance between parabola and line segment is less than max_dist.
							point_stack.pop();
							CT inter_x = (segm_vec_x * new_x - segm_vec_y * new_y) /
								sqr_segment_length + cast(x(low(segment)));
							CT inter_y = (segm_vec_x * new_y + segm_vec_y * new_x) /
								sqr_segment_length + cast(y(low(segment)));
							discretization->push_back(Point<CT>(inter_x, inter_y));
							cur_x = new_x;
							cur_y = new_y;
						}
						else {
							point_stack.push(mid_x);
						}
					}

					// Update last point.
					discretization->back() = last_point;
				}

		private:
			// Compute y(x) = ((x - a) * (x - a) + b * b) / (2 * b).
			static CT parabola_y(CT x, CT a, CT b) {
				return ((x - a) * (x - a) + b * b) / (b + b);
			}

			// Get normalized length of the distance between:
			//   1) point projection onto the segment
			//   2) start point of the segment
			// Return this length divided by the segment length. This is made to avoid
			// sqrt computation during transformation from the initial space to the
			// transformed one and vice versa. The assumption is made that projection of
			// the point lies between the start-point and endpoint of the segment.
			template <class InCT,
				template<class> class Point,
				template<class> class Segment>
			static
				typename enable_if<
				typename gtl_and<
				typename gtl_if<
				typename is_point_concept<
				typename geometry_concept< Point<int> >::type
				>::type
				>::type,
				typename gtl_if<
				typename is_segment_concept<
				typename geometry_concept< Segment<long> >::type
				>::type
				>::type
				>::type,
				CT
				>::type get_point_projection(
				const Point<CT>& point, const Segment<InCT>& segment) {
					CT segment_vec_x = cast(x(high(segment))) - cast(x(low(segment)));
					CT segment_vec_y = cast(y(high(segment))) - cast(y(low(segment)));
					CT point_vec_x = x(point) - cast(x(low(segment)));
					CT point_vec_y = y(point) - cast(y(low(segment)));
					CT sqr_segment_length =
						segment_vec_x * segment_vec_x + segment_vec_y * segment_vec_y;
					CT vec_dot = segment_vec_x * point_vec_x + segment_vec_y * point_vec_y;
					return vec_dot / sqr_segment_length;
				}

			template <typename InCT>
			static CT cast(const InCT& value) {
				return static_cast<CT>(value);
			}
		};
	}
}

#endif  // BOOST_POLYGON_VORONOI_VISUAL_UTILS
